In many conventional memory systems, such as random access memory, binary digits (bits) are stored in memory cells, and are accessed by a processor that specifies a linear address that is associated with the given cell. This system provides rapid access to any portion of the memory system within certain limitations. To facilitate processor control, each operation that accesses memory must declare, as a part of the instruction, the address of the memory cell/cells required. Standard memory systems are not well designed for a content based search. Content based searches in standard memory require a software based algorithmic search under the control of the microprocessor. Many memory operations are required to perform a search. These searches are neither quick nor efficient in using processor resources.
To overcome these inadequacies an associative memory system called Content Addressable Memory (CAM) has been developed. CAM allows cells to be referenced by their contents, so it has first found use in lookup table implementations such as cache memory subsystems and is now rapidly finding use in networking systems. CAM's most valuable feature is its ability to perform a search and compare of multiple locations as a single operation, in which search data is compared with data stored within the CAM. Typically search data is loaded onto search lines and compared with stored words in the CAM. During a search-and-compare operation, a match or mismatch signal associated with each stored word is generated, indicating whether the search word matches a stored word or not.
A CAM stores data in a matrix of cells, which are generally either SRAM based cells or DRAM based cells. Until recently, SRAM based CAM cells have been most common because of their simple implementation. However, to provide ternary state CAMs, ie. where the search and compare operation returns a “0”, “1” or “don't care” result, ternary state SRAM based cells typically require many more transistors than a DRAM based cells. As a result, ternary state SRAM based CAMs have a much lower packing density than ternary DRAM cells.
To provide the desired search and compare function in a DRAM or SRAM based CAM, matchline sensing circuits are required. Each matchline sensing circuit returns the appropriate state of its matchline, and the outputs of each matchline sensing circuit can be subsequently processed to determine the number of matches.
The circuit responsible for determining the existence of a match is the multiple match detection circuit. The multiple match detection circuit receives all the matchline sense circuit outputs as input signals after the search-and-compare operation, and determines one of two states. The first possible state represents the case where the search word does not match with any stored words or matches only one stored word. The second state occurs if the search word has matched with two or more stored words. The second state is significant because only one address of a matching word is returned as the resulting address of the search-and-compare operation. In such a case, if more than one match has resulted from the search-and-compare operation, there is at least one other stored word that matched the search word.
A prior art multiple match detection circuit and scheme is disclosed in commonly owned U.S. Pat. No. 6,307,798 titled Circuit and Method for Multiple Match Detection in Content Addressable Memory, filed Apr. 24, 2000, the contents of which are incorporated herein by reference. In the multiple match detection circuit of the prior art, a multiple matchline is precharged to a high voltage level, VDD for example, and subsequently discharged when there is at least one matchline sense circuit which outputs a signal indicating a match condition. There is one discharge transistor for each matchline sensing circuit output, and all discharge transistors are connected to the multiple matchline and in parallel with each other.
The multiple match detection circuit of the prior art compares the multiple matchline voltage level to a reference voltage during a sensing period in order to differentiate between the two different states. The reference voltage is fixed to mimic a multiple matchline having only one match, hence the multiple match detection circuit will sense if the multiple matchline voltage level is either above or below the reference voltage to generate the output corresponding to the first and second states respectively. The multiple match detection circuit therefore detects the discharged multiple match line to generate an output representing one of either the first and second states.
There are several disadvantages in the multiple match detection circuit and scheme of the prior art. To reduce the silicon area occupied by the multiple match detection circuit, it is desirable to minimize the feature size of the discharge transistors. Since the current strength of a transistor changes directly with its feature size, the capacity of a small discharge transistor to pull a fully precharged matchline to ground is small. This results in very slow discharge of the multiple matchline, and increases the time required for the overall search and compare operation of the CAM. Inherent parasitic capacitance of the multiple matchline compounds this problem, which increases as CAM arrays store more words, and require more discharge transistors.
The optimal sensing margin for the multiple match detection circuit should be sufficient for the circuit to easily distinguish if the multiple matchline potential level is above or below the reference voltage. This optimal sensing margin is attained at the time when the multiple matchline voltage level has decreased to a potential level well below the reference voltage. Unfortunately, the poor voltage discharge rate of the multiple matchline previously described only allows accurate sensing to be performed at a relatively prolonged time after the multiple matchline voltage begins to fall.
The multiple match detection circuit and scheme of the prior art requires precise timing control between activation of the matchline sense circuits, activation of the reference voltage generator circuit and activation of the sense circuit within the multiple match detection circuit. Each above-mentioned circuit is activated in sequence according to specific, preset time delays, which are determined from the design parameters and simulations. Process variations during fabrication of the CAM chip and different operating conditions may cause slight shifts in the time delays, resulting in a false output from the multiple match detection circuit.
There is clearly a need for a mutliple match detection circuit capable of consuming very little power and detecting multiple matchline potential levels accurately at high speed.